1. Field of the Invention
The present invention relates, generally, to network routing schemes, and more particularly, to the provisioning of networks so as to achieve robustness to traffic variation.
2. Description of the Related Art
With the rapid rise in new Internet-based applications, such as peer-to-peer and voice-over-IP (Internet Protocol), the accommodation of widely-varying traffic patterns in networks has become increasingly important. Accordingly, it has also become increasingly important for Internet Service Providers (ISPs) to accurately monitor traffic and to deploy mechanisms for adapting network routing to changing traffic patterns. This dynamic adaptation increases the complexity of network operations. To avoid this complexity, service providers should provision their networks such that the provisioning is robust to large changes in traffic patterns. One model to enable such provisioning is known as the “hose-traffic model” or “hose model,” which is described in N. G. Duffield et al., “A flexible model for resource management in virtual private network,” ACM SIGCOMM 1999, August 1999, incorporated herein by reference. In the hose model, the assumption is that there is knowledge regarding the maximum traffic entering and leaving the network at each node, but no knowledge of the actual traffic matrix itself. Several algorithms for routing traffic in the hose model have recently been proposed by Duffield and others, including T. Erlebach et al., “Optimal Bandwidth Reservation in Hose-Model VPNs with Multi-Path Routing,” IEEE Infocom 2004, March 2004, and A. Kumar et al., “Algorithms for provisioning VPNs in the hose model,” ACM SIGCOMM2001, August 2001, both incorporated herein by reference. These schemes route traffic directly from source nodes to destination nodes along fixed paths.
A recently proposed approach is two-phase routing, as described in M. Kodialam et al., “Efficient and Robust Routing of Highly Variable Traffic,” Third Workshop on Hot Topics in Networks (HotNets-III), November 2004, and R. Zhang-Shen et al., “Designing a Predictable Internet Backbone Network,” Third Workshop on Hot Topics in Network (HotNets-III), November 2004, both incorporated herein by reference. In the first phase of a two-phase routing scheme, incoming traffic is sent from the source to a set of intermediate nodes in predetermined proportions. In the second phase, incoming traffic is routed from the intermediate nodes to the final destination. The proportion of traffic that is distributed to each intermediate node in the first phase can depend on the intermediate nodes.
The two-phase routing scheme is flexible because it can handle wide traffic variations and is useful for various networking applications, such as service overlays with bandwidth guarantees, virtual private networks, routing through middleboxes (intermediate devices performing functions other than the normal, standard functions of an IP router on a datagram path between a source host and a destination host) for security, and IP-over-optical networks with a statically-configured transport layer.
For the IP-over-optical network application, because of static provisioning at the optical layer, neither the paths nor their associated bandwidths change with shifts in traffic. Two-phase routing meets these criteria, while direct source-destination-path routing does not. An important innovation of the two-phase routing scheme is the handling of traffic variability in a capacity-efficient manner through static preconfiguration of the network and without requiring either (i) measurement of traffic in real-time or (ii) reconfiguration of the network in response to changes in traffic.